#include <stdio.h>
#include <stdlib.h>

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MVNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef char VerTexType;      //假设顶点的数据类型为字符型 
typedef int ArcType;          //假设边的权值类型为整型 

typedef struct{ 
  VerTexType vexs[MVNum];     //顶点表 
  ArcType arcs[MVNum][MVNum]; //邻接矩阵 
  int vexnum, arcnum;         //图的当前点数和边数 
} MGraph; 

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
	int i;
	for(i=0;i<8;i++){
		if(G->vexs[i] == vertex_name){
		return i;
		}
	}
  return -1;
}

//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
  FILE * fp;
  size_t len = 0;
  ssize_t read;

  int num_nodes, num_edges;

  // 打开由 graph_data_filename变量 指定的文件名
  fp = fopen(graph_data_filename, "r");
  if (fp == NULL)
    exit(EXIT_FAILURE);

  // 从文件名由 graph_data_filename 变量所指定的文件里读取顶点数和边数
  // fscanf函数 的用法类似scanf
  fscanf(fp, "%d %d\n", &num_nodes, &num_edges);

  printf("节点数为:%d\n边数为:%d\n",num_nodes,num_edges);
    int j,h;
    (*G_pp)=(MGraph*) malloc(sizeof (MGraph));
    MGraph *gpp = *G_pp;
    for (j = 0; j < num_nodes; j++) {
        gpp->vexs[j]=fgetc(fp);
        fgetc(fp);
        printf("%c ",gpp->vexs[j]);
    }
    printf("\n");
    for (j = 0; j < num_nodes; j++) {
        for (h = 0; h < num_nodes; h++) {
            gpp->arcs[j][h]=0;
        }
    }
    char v1,v2;
    for (int k = 0; k < num_edges; k++) {
        v1 = fgetc(fp);
        printf("%c",v1);
        fgetc(fp);
        v2 = fgetc(fp);
        fgetc(fp);
        printf("%c\n",v2);
        for (j = 0; j < num_nodes; j++) {
            for (h = 0; h < num_nodes; h++) {
                if (gpp->vexs[h]==v2&&gpp->vexs[j]==v1){
                    gpp->arcs[j][h]=1;
                    gpp->arcs[h][j]=1;
                }
            }
        }
    }
    printf("邻接矩阵如下：\n");
    for (j = 0; j < num_edges; j++) {
        for (h = 0; h < num_edges; h++) {
            printf("%d\t",gpp->arcs[j][h]);
        }
        printf("\n");
    }

  // 后续的内容读取参考上一句 fscanf 函数

  // 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用

  // 如上，用fscanf从fp里读取字符

  // 实现结束


  // 关闭打开的文件
  fclose(fp);
}

//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph类型的变量的指针。
// 参数 i: 当前被访问的顶点 i。i是顶点在给出的 顶点名字序列 里从0开始的位置编号：比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 result_sequence: 用于记录在 当全局访问顺序为 visited_order 时，被访问的结点名字（字符）。
// 参数 visited_order: 当前顶点被访问的全局顺序
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{ 
	int j;
    result_sequence[*visited_order]=G->vexs[i];
    (*visited_order)++;
    visited[i]=TRUE;
    for(j=0;j<8;j++){
        if(G->arcs[i][j]==1 && ! visited[j]){
            dfs(G,j,visited,result_sequence,visited_order);  
        }
    }

}

//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 当前被访问的顶点 k。k是顶点在给出的 顶点名字序列 里从0开始的位置编号；比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字（字符）
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{ 
	 int i, j = 0, r = 0, f = 0;
    char dl[MVNum];
    for (i = 0; i < MVNum; i++) {
        visited[i] = FALSE;
        visited_sequence[i] = 0;
        dl[i] = 0;
    }
    dl[r] = G->vexs[k];
    visited[k] = TRUE;
    while (dl[r] != 0) {
        for (i = 0; i < 8; i++) {
			if (G->arcs[k][i] == 1 && visited[i] == FALSE) {
                f++;
                visited[i] = TRUE;
                dl[f] = G->vexs[i];
            }
        }
        visited_sequence[j] = dl[r];
        r++;
        k = locate_vertex(G, dl[r]);
        j++;
    }

}

// 以下 main 函数的实现，供参考。

int main () {
  int i;
  MGraph *G;
  Boolean visited[MVNum];

  create_graph(&G, "graph_data.txt"); //建立邻接矩阵

  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char dfs_sequence[MVNum] = {'\0'};
  int visited_order = 0;
  dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
  printf("Print Graph DFS: ");
  printf("%s\n", dfs_sequence);
  printf("\n");
  
  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char bfs_sequence[MVNum] = {'\0'};
  bfs(G, 0, visited, bfs_sequence); //以序号为3的顶点开始广度优先遍历。应该输出：abcdefgh
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence);
  printf("\n");
  
  for(i=0; i<MVNum; i++) {
    visited[i] = FALSE;
  }
  char bfs_sequence2[MVNum] = {'\0'};
  bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence2);
  printf("\n");

  return 0;
}
